#include<stdio.h>
#include<time.h>
#include<math.h>

struct NODE{
    NODE* prev;
    NODE* next;
};


void list_init(NODE* node){
    node->prev = node->next = node;
}

void _list_add(NODE* node, NODE* prev, NODE* next){
    prev->next = node;
    next->prev = node;
    node->prev = prev;
    node->next = next;
}

void list_add(NODE* node, NODE* pos){
    _list_add(node, pos, pos->next);
}

struct OD
{
    NODE node;
    int value;
};

#define MAX_DB 1000
#define node2od(node) ((OD*)(node))

void printList(NODE* root){
    NODE* node = root->next;
    while(node!=root){
        auto tmp = node2od(node);
        node = node->next;
        printf("%d ", tmp->value);
    }
    printf("\n");
}

int GetTopK(NODE* root, int K, int* output);

OD db[MAX_DB];
NODE list_root;

int main(){

    list_init(&list_root);

    int arr[10] = {-100, 5, -7, 0, 7, 10, 22, 18, 80, 31};
    for(int i=0;i<10;i++){
        OD* od = &db[i];
        od->value = arr[i];
        list_add(&od->node, list_root.prev);
    }

    printList(&list_root);

    int result[20];
    int ret = GetTopK(&list_root, 2, result);

    for(int i=0;i<ret;i++ ) printf("%d ", result[i]);
    printf("\n");
}


int GetTopK(NODE* root, int K, int* output){
    NODE* node = root->next;
    if(node==root) return 0;      // Empty List
    int EMPTY=0x7fffffff;
    for(int i=0;i<K;i++) output[i] = EMPTY;
    // First element of List
    output[0] = node2od(node)->value;
    node = node->next;
    int ret = 1;
    while (node!=root){
        int cur_value = node2od(node)->value;
        node = node->next;
        ret++;
        for(int i=0;i<K;i++){
            if(output[i]!=EMPTY){
                if(cur_value > output[i]){
                    // move elements
                    for(int j=K-1;j>i;j--){
                        output[j] = output[j-1];
                    }
                    output[i] = cur_value;
                    break;
                }
            }else{
                output[i] = cur_value;
                break;
            }
        }
    }
    return ret>K?K:ret;
}


void bubble_sort(int* arr, int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(arr[j+1] > arr[j]){
                // swap
                int tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}
